package com.yiwenup.leetcode.hot;

/**
 * @PROJECT struct-algorithm
 * @PACKAGE com.yiwenup.leetcode.hot
 * @Author yiwenup
 * @Date 2022-03-14 21:25:24
 * <p>
 * @DESCRIPTION https://leetcode-cn.com/problems/burst-balloons/
 */
public class No0312 {

    /**
     * 执行用时：27 ms, 在所有 Java 提交中击败了99.86%的用户
     * 内存消耗：40.9 MB, 在所有 Java 提交中击败了45.76%的用户
     */
    public int maxCoins(int[] nums) {
        int n = nums.length + 2;
        int[] tmp = new int[n];
        tmp[0] = tmp[n - 1] = 1;

        for (int i = 0; i < nums.length; i++) {
            tmp[i + 1] = nums[i];
        }

        int[][] dp = new int[n][n];

        // len: 开区间的长度
        for (int len = 3; len <= n; len++) {
            // j: 右界
            for (int j = len - 1; j < n; j++) {
                int coins = 0;
                // i: 左界
                int i = j - len + 1;

                int p = tmp[i] * tmp[j];
                for (int k = i + 1; k < j; k++) {
                    coins = Math.max(coins, dp[i][k] + p * tmp[k] + dp[k][j]);
                }
                dp[i][j] = coins;
            }
        }

        return dp[0][n - 1];
    }
}
